2

Computational complexity via programming languages: constant factors do matter

Year:
2000
Language:
english
File:
PDF, 224 KB
english, 2000
3

On pointers versus addresses

Year:
1992
Language:
english
File:
PDF, 2.19 MB
english, 1992
4

What is a “pointer machine”?

Year:
1995
Language:
english
File:
PDF, 527 KB
english, 1995
6

Unit-cost pointers versus logarithmic-cost addresses

Year:
1994
Language:
english
File:
PDF, 607 KB
english, 1994
7

Topological Lower Bounds on Algebraic Random Access Machines

Year:
2001
Language:
english
File:
PDF, 368 KB
english, 2001
8

Lower Bounds for Dynamic Data Structures on Algebraic RAMs

Year:
2002
Language:
english
File:
PDF, 269 KB
english, 2002
12

When Can We Sort ino(n log n) Time?

Year:
1997
Language:
english
File:
PDF, 2.29 MB
english, 1997
13

A simple and efficient Union–Find–Delete algorithm

Year:
2011
Language:
english
File:
PDF, 202 KB
english, 2011
14

Tighter constant-factor time hierarchies

Year:
2003
Language:
english
File:
PDF, 89 KB
english, 2003
15

Improved Bounds for Functions Related to Busy Beavers

Year:
2002
Language:
english
File:
PDF, 82 KB
english, 2002
16

Element distinctness on one-tape Turing machines: a complete solution

Year:
2003
Language:
english
File:
PDF, 133 KB
english, 2003
17

A complexity tradeoff in ranking-function termination proofs

Year:
2009
Language:
english
File:
PDF, 325 KB
english, 2009
18

A note on busy beavers and other creatures

Year:
1996
Language:
english
File:
PDF, 577 KB
english, 1996
23

A Generalization of a Lower Bound Technique due to Fredman and Saks

Year:
2001
Language:
english
File:
PDF, 180 KB
english, 2001
29

On the Termination of Integer Loops

Year:
2012
Language:
english
File:
PDF, 212 KB
english, 2012
30

Program termination analysis in polynomial time

Year:
2007
Language:
english
File:
PDF, 380 KB
english, 2007
33

Backing up in singly linked lists

Year:
2006
Language:
english
File:
PDF, 202 KB
english, 2006
34

Ranking Functions for Linear-Constraint Loops

Year:
2014
Language:
english
File:
PDF, 588 KB
english, 2014
36

Size-change termination with difference constraints

Year:
2008
Language:
english
File:
PDF, 243 KB
english, 2008
39

The Church-Turing thesis and its look-alikes

Year:
2005
Language:
english
File:
PDF, 438 KB
english, 2005
41

A complexity-theoretic proof of a Recursion-Theoretic Theorem

Year:
2004
Language:
english
File:
PDF, 57 KB
english, 2004
42

Stable closed-loop fiber-optic delay of arbitrary radio-frequency waveforms

Year:
2015
Language:
english
File:
PDF, 1.81 MB
english, 2015